package hot100;

import java.util.HashSet;
import java.util.Set;

public class detectCycle4 {
    public mergeKLists.ListNode detectCycle2(mergeKLists.ListNode head) {
        Set<mergeKLists.ListNode> set = new HashSet<>();
        while(head != null) {
            if(!set.contains(head)) {
                set.add(head);
            }else {
                return head;
            }
            head = head.next;
        }
        return null;
    }
    public mergeKLists.ListNode detectCycle(mergeKLists.ListNode head) {
        //快慢指针，相遇两轮，第一轮为环中
        mergeKLists.ListNode slow = head;
        mergeKLists.ListNode fast = head;
        while (true) {
            //第一轮中，要么两张相遇，要么fast为空
            if(fast == null || fast.next == null) return null;
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                break;
            }

        }
        //第二轮，找到环入口，一定存在环
        fast = head;
        while(slow != fast ) {
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }
}
